<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8">
<title>数组算法-算法合集</title>
</head>
<body>
<script>
console.log('----------------------两个数组的交集----------------------');
var intersect = function(nums1, nums2) {
    var ret = [];
    var obj = {};
    var index;
    for(var i = 0; i < nums1.length; i++) {
        var item = nums1[i];
        var startIndex = obj[item];
        if(obj[item] == undefined) {
        	startIndex = -1;
        }
        
        index = nums2.indexOf(item, startIndex + 1);
        obj[item] = Math.max(startIndex, index);
        
        if(index > -1) {
        	ret.push(item);
        }
    }
    return ret;
};
console.log('intersect:', intersect([3, 3, 4, 3, 5], [3, 5, 8, 3, 9]));//[3,3,5]
</script>
<script>
// 两个数相加得出目标值,并返回这两个数的下标
var twoSum = function(nums, target) {
    var total;
    var ret = [];

    for(var i = 0; i < nums.length; i++) {
        total = nums[i];
        for(var j = i + 1; j < nums.length; j++) {
            if((total + nums[j]) == target) {
                ret = [i, j];
            }
        }  
    }

    return ret;
};
var nums = [2,11,15,7], target = 9;
console.log('twoSum:', twoSum(nums, target));
</script>
<script type="text/javascript">
var runningSum = function(nums) {
    var ret = [];
    for(var i = 0; i < nums.length; i++) {
        var total = 0;
        for(var j = 0; j <= i; j++) {
            total += nums[j];
        }
        ret.push(total);
    }

    return ret;
};
console.log('runningSum:', runningSum([1,1,1,1,1]));
</script>
<script type="text/javascript">
var hammingWeight = function(n) {

    var str = n.toString(2);
    var i = 0;
    var num = str.indexOf('1');
    while(num > -1) {
        i++;
        num = str.indexOf('1', num + 1);
    }

    return i; 
};
console.log(hammingWeight(3324));
</script>
<script type="text/javascript">
var numberOfSteps  = function(num) {
    var n = 0;
    while(num !== 0) {
        if((num % 2) == 0) {
            num = parseInt(num / 2);
        }else {
            num = num - 1;
        }
        n++;
    }

    return n;
};
console.log(numberOfSteps(5));
</script>
<script type="text/javascript">
var sumNums = function(n) {
    var addNum = function(total, startNum) {
        return (n < startNum) ? (total) : (addNum(total + startNum, startNum + 1));;
    };

    return addNum(0, 1);
};
console.log(sumNums(9));
</script>
<script type="text/javascript">
var NestedIterator = function(nestedList) {
    let ret = [];
    this.nestedList = nestedList;
    this.nextIndex = 0;
    this.hadNextNum = 0;//已读取的数量
    this.nextItem = null;
    this.nestedLen = this.nestedList.length;

    this.isInteger = function(item) {
        item = item || this.nestedList[this.nextIndex];
        if(typeof item == 'number') {
            return true;
        }

        return false;
    }
    this.getInteger = function() {
        let nextItem = this.nestedList[this.nextIndex];
        this.nextIndex = this.nextIndex + 1;
        this.hadNextNum = this.hadNextNum + 1;
        this.nextItem = this.nestedList[this.nextIndex] || null;
        return nextItem;
    }
    this.getList = function() {
        return this.nestedList[this.nextIndex];
    }
};


/**
 * @this NestedIterator
 * @returns {boolean}
 */
NestedIterator.prototype.hasNext = function() {
    let count = 0;
    let nestedList = this.nestedList;

    for(let i = 0; i < nestedList.length; i++) {
        let item = nestedList[i];
        if(typeof item == 'number') {

        }else {//数组

        }
    }
};

/**
 * @this NestedIterator
 * @returns {integer}
 */
NestedIterator.prototype.next = function() {
    if(this.isInteger()) {
        return this.getInteger();
    }else {

    }
};

var i = new NestedIterator([1,[4,[6]]]), 
    a = [];
if (i.hasNext()) {
    a.push(i.next());  
} 
console.log(a);
</script>
<script type="text/javascript">
var hammingDistance = function(x, y) {
    let fronStr = '';
    for(let j = 0; j <32; j++) {
        fronStr += '0';
    }
    const x1 = (fronStr + x.toString('2')).slice(0 -32);
    const y1 = (fronStr + y.toString('2')).slice(0 -32);
    let x1Len = x1.length;
    let y1Len = y1.length;
    let count = 0;
    let maxL = 32;

    for(let i = maxL; i > 0; i--) {
        if(x1[i] !== y1[i]) {
            count++;
        }
    }

    return count;
};
console.log(hammingDistance(1, 4));
</script>
<script type="text/javascript">
var singleNumber = function(nums) {
    let obj = {};
    let res;

    for(let i = 0; i < nums.length; i++) {
        let item = nums[i];
        obj[item] = (obj[item] || 0) + 1;
    }
    for(let key in obj) {
        if(obj[key] == 1) {
            res = key;
        }
    }

    return res;
};
console.log('singleNumber:', singleNumber([4,1,2,1,2]));
</script>
<script type="text/javascript">
var majorityElement = function(nums) {
    let len1 = nums.length;
    let len2 = len1 / 2;
    let obj = {};
    let res;

    for(let i = 0; i < len1; i++) {
        let item = nums[i];
        obj[item] = (obj[item] || 0) + 1;
    }

    for(let key in obj) {
        if(obj[key] > len2) {
            res = key;
        }
    }

    return res;
};
console.log('majorityElement:', majorityElement([3,2,3]))
</script>
<script type="text/javascript">
var moveZeroes = function(nums) {
    const len = nums.length;

    for(let i = len - 1; i >= 0; i--) {
        let item = nums[i];
        if(item == 0) {
            nums.splice(i, 1);
            nums.push(0);
        }
    }

    return nums;
};
console.log('moveZeroes:', moveZeroes([0,1,0,3,12,0]))
</script>
<script type="text/javascript">
var findDisappearedNumbers = function(nums) {
    let ret = [];
    let len = nums.length;

    for(let i = 1; i <= len; i++) {
        if(!nums.includes(i)) {
            ret.push(i);
        }
    }

    return ret;
};
console.log('findDisappearedNumbers:', findDisappearedNumbers([4,3,2,7,8,2,3,1]))
console.log('findDisappearedNumbers:', findDisappearedNumbers([1, 1]))
</script>
<script type="text/javascript">
var findDuplicate = function(nums) {
    let len = nums.length;
    for(let i = 0; i < len; i++) {
        let item = nums[i];
        if(nums.indexOf(item) !== nums.lastIndexOf(item)) {
            return item;
        }
    }
};

console.log('findDuplicate:');
console.log(findDuplicate([1,3,4,2,2]));
</script>
<script type="text/javascript">
var dailyTemperatures = function(T) {
    let ret = [];
    let len = T.length;

    for(let i = 0; i < len; i++) {
        let num = 0;
        let item1 = T[i];
        for(let j = i + 1; j < len; j++) {
            let item2 = T[j];
            if(item2 > item1) {
                num = j - i;
                break;
            }
        }

        ret.push(num);
    }

    return ret;
};
console.log('dailyTemperatures:', dailyTemperatures([73, 74, 75, 71, 69, 72, 76, 73]))
</script>
<script type="text/javascript">
var topKFrequent = function(nums, k) {
    let map = {};
    let res = [];
    let arr = [];
    let len = nums.length;

    for(let i = 0; i < len; i++) {
        let item = nums[i];
        map[item] = (map[item] || 0) + 1;
    }
    
    for(let key in map) {
        arr.push({
            key: parseInt(key),
            val: map[key],
        })
    }

    arr.sort((item1, item2) => {
        return item2.val - item1.val;
    });

    for(let j = 0; j < k; j++) {
        res.push(arr[j].key);
    }

    return res;
};
console.log('topKFrequent:', topKFrequent([1,2], 2))
console.log('topKFrequent:', topKFrequent([1,1,1,2,2,3], 2))
</script>
</body>
</html>